/*
 * @lc app=leetcode.cn id=689 lang=typescript
 *
 * [689] 三个无重叠子数组的最大和
 */

// @lc code=start
function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
  const ans = new Array(3).fill(0);
  let sum1 = 0,
    maxSum1 = 0,
    maxSum1Index = 0;
  let sum2 = 0,
    maxSum12 = 0,
    maxSum12Index1 = 0,
    maxSum12Index2 = 0;
  let sum3 = 0,
    maxSum123 = 0;

  for (let i = 2 * k; i < nums.length; i++) {
    sum1 += nums[i - 2 * k];
    sum2 += nums[i - k];
    sum3 += nums[i];
    // 开始滑动窗口
    if (i >= 3 * k - 1) {
      // 更新第一个子数组的最大和
      if (sum1 > maxSum1) {
        maxSum1 = sum1;
        maxSum1Index = i - 3 * k + 1;
      }
      // 更新第二个子数组的最大和
      if (maxSum1 + sum2 > maxSum12) {
        maxSum12 = maxSum1 + sum2;
        maxSum12Index1 = maxSum1Index;
        maxSum12Index2 = i - 2 * k + 1;
      }
      // 更新第三个子数组的最大和以及答案
      if (maxSum12 + sum3 > maxSum123) {
        maxSum123 = maxSum12 + sum3;
        ans[0] = maxSum12Index1;
        ans[1] = maxSum12Index2;
        ans[2] = i - k + 1;
      }
      // 左边移除一个元素
      sum1 -= nums[i - 3 * k + 1];
      sum2 -= nums[i - 2 * k + 1];
      sum3 -= nums[i - k + 1];
    }
  }

  return ans;
}
// @lc code=end
